星尘

LeetCode - 209. 长度最小的子数组

发表于 更新于 分类于

209. 长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例 1:

1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2:

1
2
输入：target = 4, nums = [1,4,4]
输出：1

示例 3:

1
2
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def minSubArrayLen(self, target, nums):
        # 左指针和右指针都是从 0 开始
        left = 0
        right = 0
        # 最大程度设置为一个无限大的数，因为后面要比较谁短，所以这里长度不能小于等于数组长度。不然区分不出是默认值还是真正存在的数据长度
        min_len = float("inf")
        # 和值默认设置为 0
        sum_value = 0
        # 循环条件是右指针没有走到最后
        while right < len(nums):
            # 计算左右指针之间的值(滑动窗口的值)
            sum_value += nums[right]
            # 如果两者之间的值大于了目标值，那么就缩小窗口的大小, 及左指针往右移
            while sum_value >= target:
                # 计算当前的窗口的长度，并与之前的比较，看看窗口长度是现在的小还是以前的小，保存小的一个给 min_len
                min_len = min(min_len, right - left + 1)
                # 左指针右移, 所以 sum_value 值要相对应减少
                sum_value -= nums[left]
                left += 1
            # 右指针正常往前走
            right += 1

        return 0 if min_len == float("inf") else min_len
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func minSubArrayLen(target int, nums []int) int {
	left := 0
	right := 0
	minLen := len(nums) + 1
	sumValue := 0

	for right < len(nums){
		sumValue += nums[right]
		for sumValue >= target{
			minLen = int(math.Min(float64(minLen), float64(right-left+1)))
			sumValue -= nums[left]
			left += 1
		}
		right += 1
	}

	if minLen == len(nums) + 1{
		return 0
	}
	return minLen
}

变体

总结

左右指针同时从0位置出发，右指针右移，扩大滑动窗口的值，如果滑动窗口的和值大于 target，那么就计算滑动窗口的长度，将滑动的窗口的长度和之前的比较，取最小的。之后需要缩小滑动窗口，即左指针往后走，如此反复，直到右指针走到最后，且滑动窗口的值已经不能超过 target 了。

最后获取最小的滑动窗口的长度，如果没有则返回默认值。

参考